package com.datastructure.sort.self;

public class QuickSort {

    public static void main(String[] args) {
        int [] arr = {78,24,69,56,12,35,78};
        QuickSort quickSort = new QuickSort();
        quickSort.quick_sort(arr,0,arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
        }
    }

    public void quick_sort(int[] a,int l,int r){
        if (l < r)
        {
            int i,j,x;

            i = l;
            j = r;
            x = a[i];
            while (i < j)
            {
                while(i < j && a[j] > x)
                    j--; // 从右向左找第一个小于x的数
                if(i < j)
                    a[i++] = a[j];
                while(i < j && a[i] < x)
                    i++; // 从左向右找第一个大于x的数
                if(i < j)
                    a[j--] = a[i];
            }
            a[i] = x;
            quick_sort(a, l, i-1); /* 递归调用 */
            quick_sort(a, i+1, r); /* 递归调用 */
        }
    }
}
